package Z代码随想录.数组;

// 最小覆盖子串

public class Leetcode76 {
    // 本题思路是利用滑动窗口来进行求解
    // 首先记录 用一个countT统计数组 来记录 T中每个字符出现的次数，另外一个统计数组countS来记录S中字符是在 T中出现的字符的个数
    // 定义一个 right右指针，依次往后，如果当前S中的字符不在 T中，就直接跳过，right++
    // 如果在T中，并且当前字符在countS中次数 严格小于 countT中出现的次数 ，然后就将countS[ch]++, right继续往后走
    // 当 count == t.length的时候，只有当 min 的值 小于 right -left的时候才记录当前的 子序列的长度，并将 begin = left
    // 然后开始 left 向左，如果该字符没有在T出现过，就continue, left++ 如果出现了，就将 countS[ch2]--
    // 如果 此时countS[ch2]== countT[ch2]，就 count--，再left++;
    // 此时 count != t.length， 就开始新的 right了
    public static String minWindow(String s, String t) {
        if (s == null || s == "" || t == null || t == "" || s.length() < t.length()) {
            return "";
        }
        int[] countT = new int[128];  // 用来保存 T 中字符出现的次数
        int[] countS = new int[128];  // 用来保存 S 中字符出现的次数
        // 先保存 t 中的每个字符出现次数
        for (char ch : t.toCharArray()) {
            countT[ch]++;
        }

        int left = 0; // 起始位置
        int right = 0; // 结束位置
        int min = s.length() + 1;  // 定义一个初始长度，永远也不可能达到的
        int count = 0; // 在S中找到一个T中的字符就+1
        int begin = 0; // 记录初始位置

        while (right < s.length()) {
            // 开始向后滑动 right
            // 如果字符不在 counT中出现过就 continue，不执行下面逻辑
            char ch = s.charAt(right);
            if (countT[ch] == 0) {
                right++;
                continue;
            }
            // 只有严格出现S中该字符出现的次数小于 T中该字符出现时候， 才能加1
            // 不能就 S中出现一个T中的字符个数加count++,可能出现的是重复的
            if (countS[ch] < countT[ch]) {
                count++;
            }
            // 执行到这说明，出现的当前字符是 T 中包含的，此时记录 countS[right]
            countS[ch]++;
            right++;

            // 下一步，就是考虑，当count == T.length 的时候，就要开始 动 left ，缩小窗口大小
            while (count == t.length()) {
                // 此时就要计算当前 子序列的长度
                if (right - left < min){
                    min = right -left;
                    begin = left;
                }
                // 然后开始滑动窗口
                char ch2 = s.charAt(left);
                if (countS[ch2] == 0) {
                    left++;
                    continue;
                }
                // 此时当前该字符出现的次数正好等于T中出现字符次数就 count--
                if (countS[ch2]==countT[ch2]){
                    count--;
                }
                // 此时left 指向的字符是在T中出现的,我们就要进行减少该字符出现的一次
                countS[ch2]--;
                left++;
            }
        }
        return min == (s.length() + 1) ? "" : s.substring(begin, begin + min);
    }

    public static void main(String[] args) {
        String s = "ADOBECODEBANC";
        String t = "ABC";
        String ret = minWindow(s,t);
        System.out.println(ret);
    }
}
